home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / networking / ip / ka9q / src890906.arc / IPROUTE.C < prev    next >
C/C++ Source or Header  |  1989-09-07  |  15KB  |  589 lines
  1. /* Lower half of IP, consisting of gateway routines
  2.  * Includes routing and options processing code
  3.  */
  4. #include "global.h"
  5. #include "mbuf.h"
  6. #include "internet.h"
  7. #include "timer.h"
  8. #include "netuser.h"
  9. #include "ip.h"
  10. #include "icmp.h"
  11. #include "iface.h"
  12. #include "trace.h"
  13.  
  14. static int16 hash_ip __ARGS((int32 addr));
  15. static struct route *rt_lookup __ARGS((int32 target));
  16.  
  17. struct route *Routes[32][NROUTE];    /* Routing table */
  18. struct route R_default;            /* Default route entry */
  19.  
  20. int32 Ip_addr;
  21. struct ip_stats Ip_stats;
  22.  
  23. /* Route an IP datagram. This is the "hopper" through which all IP datagrams,
  24.  * coming or going, must pass.
  25.  *
  26.  * "rxbroadcast" is set to indicate that the packet came in on a subnet
  27.  * broadcast. The router will kick the packet upstairs regardless of the
  28.  * IP destination address.
  29.  */
  30. int
  31. ip_route(i_iface,bp,rxbroadcast)
  32. struct iface *i_iface;    /* Input interface */
  33. struct mbuf *bp;    /* Input packet */
  34. int rxbroadcast;    /* True if packet had link broadcast address */
  35. {
  36.     struct ip ip;            /* IP header being processed */
  37.     int16 ip_len;            /* IP header length */
  38.     int16 length;            /* Length of data portion */
  39.     int32 gateway;            /* Gateway IP address */
  40.     register struct route *rp;    /* Route table entry */
  41.     struct iface *iface;        /* Output interface, possibly forwarded */
  42.     int16 offset;            /* Offset into current fragment */
  43.     int16 mf_flag;            /* Original datagram MF flag */
  44.     int strict = 0;            /* Strict source routing flag */
  45.     char prec;            /* Extracted from tos field */
  46.     char del;
  47.     char tput;
  48.     char rel;
  49.     int16 opt_len;        /* Length of current option */
  50.     char *opt;        /* -> beginning of current option */
  51.     char *ptr;        /* -> pointer field in source route fields */
  52.     struct mbuf *tbp;
  53.  
  54.     Ip_stats.total++;
  55.     if(len_mbuf(bp) < IPLEN){
  56.         /* The packet is shorter than a legal IP header */
  57.         Ip_stats.runt++;
  58.         free_p(bp);
  59.         return -1;
  60.     }
  61.     /* Sneak a peek at the IP header's IHL field to find its length */
  62.     ip_len = (bp->data[0] & 0xf) << 2;
  63.     if(ip_len < IPLEN){
  64.         /* The IP header length field is too small */
  65.         Ip_stats.length++;
  66.         free_p(bp);
  67.         return -1;
  68.     }
  69.     if(cksum(NULLHEADER,bp,ip_len) != 0){
  70.         /* Bad IP header checksum; discard */
  71.         Ip_stats.checksum++;
  72.         free_p(bp);
  73.         return -1;
  74.     }
  75.     /* Extract IP header */
  76.     ntohip(&ip,&bp);
  77.  
  78.     if(ip.version != IPVERSION){
  79.         /* We can't handle this version of IP */
  80.         Ip_stats.version++;
  81.         free_p(bp);
  82.         return -1;
  83.     }
  84.     /* Trim data segment if necessary. */
  85.     length = ip.length - ip_len;    /* Length of data portion */
  86.     trim_mbuf(&bp,length);    
  87.                 
  88.     /* Process options, if any. Also compute length of secondary IP
  89.      * header in case fragmentation is needed later
  90.      */
  91.     strict = 0;
  92.     for(opt = ip.options; opt < &ip.options[ip.optlen];opt += opt_len){
  93.         /* Most options have a length field. If this is a EOL or NOOP,
  94.          * this (garbage) value won't be used
  95.          */
  96.         opt_len = uchar(opt[1]);
  97.  
  98.         switch(opt[0] & OPT_NUMBER){
  99.         case IP_EOL:
  100.             goto no_opt;    /* End of options list, we're done */
  101.         case IP_NOOP:
  102.             opt_len = 1;
  103.             break;        /* No operation, skip to next option */
  104.         case IP_SSROUTE:    /* Strict source route & record route */
  105.             strict = 1;    /* note fall-thru */
  106.         case IP_LSROUTE:    /* Loose source route & record route */
  107.             /* Source routes are ignored unless we're in the
  108.              * destination field
  109.              */
  110.             if(ip.dest != Ip_addr)
  111.                 break;    /* Skip to next option */
  112.             if(uchar(opt[2]) >= opt_len){
  113.                 break;    /* Route exhausted; it's for us */
  114.             }
  115.             /* Put address for next hop into destination field,
  116.              * put our address into the route field, and bump
  117.              * the pointer
  118.              */
  119.             ptr = opt + uchar(opt[2]) - 1;
  120.             ip.dest = get32(ptr);
  121.             put32(ptr,Ip_addr);
  122.             opt[2] += 4;
  123.             break;
  124.         case IP_RROUTE:    /* Record route */
  125.             if(uchar(opt[2]) >= opt_len){
  126.                 /* Route area exhausted; kick back an error */
  127.                 union icmp_args icmp_args;
  128.  
  129.                 icmp_args.pointer = IPLEN + opt - ip.options;
  130.                 icmp_output(&ip,bp,PARAM_PROB,0,&icmp_args);
  131.                 free_p(bp);
  132.                 return -1;
  133.             }
  134.             /* Add our address to the route */
  135.             ptr = opt + uchar(opt[2]) - 1;
  136.             ptr = put32(ptr,Ip_addr);
  137.             opt[2] += 4;
  138.             break;
  139.         }
  140.     }
  141. no_opt:
  142.  
  143.     /* See if it's a broadcast or addressed to us, and kick it upstairs */
  144.     if(ip.dest == Ip_addr || rxbroadcast){
  145. #ifdef    GWONLY
  146.     /* We're only a gateway, we have no host level protocols */
  147.         if(!rxbroadcast)
  148.             icmp_output(&ip,bp,DEST_UNREACH,PROT_UNREACH,(union icmp_args *)NULL);
  149.         free_p(bp);
  150. #else
  151.         ip_recv(i_iface,&ip,bp,rxbroadcast);
  152. #endif
  153.         return 0;
  154.     }
  155.     /* Decrement TTL and discard if zero */
  156.     if(--ip.ttl == 0){
  157.         /* Send ICMP "Time Exceeded" message */
  158.         icmp_output(&ip,bp,TIME_EXCEED,0,NULLICMP);
  159.         free_p(bp);
  160.         return -1;
  161.     }
  162.     /* Look up target address in routing table */
  163.     if((rp = rt_lookup(ip.dest)) == NULLROUTE){
  164.         /* No route exists, return unreachable message */
  165.         icmp_output(&ip,bp,DEST_UNREACH,HOST_UNREACH,NULLICMP);
  166.         free_p(bp);
  167.         return -1;
  168.     }
  169.     rp->uses++;
  170.     /* Check for output forwarding and divert if necessary */
  171.     iface = rp->iface;
  172.     if(iface->forw != NULLIF)
  173.         iface = iface->forw;
  174.  
  175.     /* Find gateway; zero gateway in routing table means "send direct" */
  176.     if(rp->gateway == (int32)0)
  177.         gateway = ip.dest;
  178.     else
  179.         gateway = rp->gateway;
  180.  
  181.     if(strict && gateway != ip.dest){
  182.         /* Strict source routing requires a direct entry */
  183.         icmp_output(&ip,bp,DEST_UNREACH,ROUTE_FAIL,NULLICMP);
  184.         free_p(bp);
  185.         return -1;
  186.     }
  187.     prec = PREC(ip.tos);
  188.     del = ip.tos & DELAY;
  189.     tput = ip.tos & THRUPUT;
  190.     rel = ip.tos & RELIABILITY;
  191.  
  192.     if(ip.length <= iface->mtu){
  193.         /* Datagram smaller than interface MTU; put header
  194.          * back on and send normally
  195.          */
  196.         if((tbp = htonip(&ip,bp)) == NULLBUF){
  197.             free_p(bp);
  198.             return -1;
  199.         }
  200.         return (*iface->send)(tbp,iface,gateway,prec,del,tput,rel);
  201.     }
  202.     /* Fragmentation needed */
  203.     if(ip.flags.df){
  204.         /* Don't Fragment set; return ICMP message and drop */
  205.         icmp_output(&ip,bp,DEST_UNREACH,FRAG_NEEDED,NULLICMP);
  206.         free_p(bp);
  207.         return -1;
  208.     }
  209.     /* Create fragments */
  210.     offset = ip.offset;
  211.     mf_flag = ip.flags.mf;        /* Save original MF flag */
  212.     while(length != 0){        /* As long as there's data left */
  213.         int16 fragsize;        /* Size of this fragment's data */
  214.         struct mbuf *f_data;    /* Data portion of fragment */
  215.  
  216.         /* After the first fragment, should remove those
  217.          * options that aren't supposed to be copied on fragmentation
  218.          */
  219.         ip.offset = offset;
  220.         if(length + ip_len <= iface->mtu){
  221.             /* Last fragment; send all that remains */
  222.             fragsize = length;
  223.             ip.flags.mf = mf_flag;    /* Pass original MF flag */
  224.         } else {
  225.             /* More to come, so send multiple of 8 bytes */
  226.             fragsize = (iface->mtu - ip_len) & 0xfff8;
  227.             ip.flags.mf = 1;
  228.         }
  229.         ip.length = fragsize + ip_len;
  230.  
  231.         /* Duplicate the fragment */
  232.         dup_p(&f_data,bp,offset,fragsize);
  233.         if(f_data == NULLBUF){
  234.             free_p(bp);
  235.             return -1;
  236.         }
  237.         /* Put IP header back on */
  238.         if((tbp = htonip(&ip,f_data)) == NULLBUF){
  239.             free_p(f_data);
  240.             free_p(bp);
  241.             return -1;
  242.         }
  243.         /* and ship it out */
  244.         if((*iface->send)(tbp,iface,gateway,prec,del,tput,rel) == -1){
  245.             free_p(bp);
  246.             return -1;
  247.         }
  248.         offset += fragsize;
  249.         length -= fragsize;
  250.     }
  251.     free_p(bp);
  252.     return 0;
  253. }
  254.  
  255. static struct rt_cache Rt_cache;
  256.  
  257. /* Add an entry to the IP routing table. Returns 0 on success, -1 on failure */
  258. int
  259. rt_add(target,bits,gateway,iface)
  260. int32 target;        /* Target IP address prefix */
  261. unsigned int bits;    /* Size of target address prefix in bits (0-32) */
  262. int32 gateway;
  263. struct iface *iface;
  264. {
  265.     struct route *rp,**hp;
  266.     int16 i;
  267.     int32 mask;
  268.  
  269.     if(iface == NULLIF)
  270.         return -1;
  271.  
  272.     Rt_cache.target = 0;    /* Flush cache */
  273.  
  274.     /* Zero bits refers to the default route */
  275.     if(bits == 0){
  276.         rp = &R_default;
  277.     } else {
  278.         if(bits > 32)
  279.             bits = 32;
  280.  
  281.         /* Mask off don't-care bits */
  282.         mask = 0xffffffff;
  283.         for(i=31;i >= bits;i--)
  284.             mask <<= 1;
  285.  
  286.         target &= mask;
  287.         /* Search appropriate chain for existing entry */
  288.         for(rp = Routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  289.             if(rp->target == target)
  290.                 break;
  291.         }
  292.     }
  293.     if(rp == NULLROUTE){
  294.         /* The target is not already in the table, so create a new
  295.          * entry and put it in.
  296.          */
  297.         if((rp = (struct route *)malloc(sizeof(struct route))) == NULLROUTE)
  298.             return -1;    /* No space */
  299.         /* Insert at head of table */
  300.         rp->prev = NULLROUTE;
  301.         hp = &Routes[bits-1][hash_ip(target)];
  302.         rp->next = *hp;
  303.         if(rp->next != NULLROUTE)
  304.             rp->next->prev = rp;
  305.         *hp = rp;
  306.     }
  307.     rp->target = target;
  308.     rp->gateway = gateway;
  309.     rp->iface = iface;
  310.     rp->uses = 0;
  311.  
  312.     return 0;
  313. }
  314.  
  315. /* Remove an entry from the IP routing table. Returns 0 on success, -1
  316.  * if entry was not in table.
  317.  */
  318. int
  319. rt_drop(target,bits)
  320. int32 target;
  321. unsigned int bits;
  322. {
  323.     register struct route *rp;
  324.     unsigned int i;
  325.     int32 mask;
  326.  
  327.     Rt_cache.target = 0;    /* Flush the cache */
  328.  
  329.     if(bits == 0){
  330.         /* Nail the default entry */
  331.         R_default.iface = NULLIF;
  332.         return 0;
  333.     }
  334.     if(bits > 32)
  335.         bits = 32;
  336.  
  337.     /* Mask off don't-care bits */
  338.     mask = 0xffffffff;
  339.     for(i=31;i >= bits;i--)
  340.         mask <<= 1;
  341.  
  342.     target &= mask;
  343.  
  344.     /* Search appropriate chain for existing entry */
  345.     for(rp = Routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  346.         if(rp->target == target)
  347.             break;
  348.     }
  349.     if(rp == NULLROUTE)
  350.         return -1;    /* Not in table */
  351.  
  352.     if(rp->next != NULLROUTE)
  353.         rp->next->prev = rp->prev;
  354.     if(rp->prev != NULLROUTE)
  355.         rp->prev->next = rp->next;
  356.     else
  357.         Routes[bits-1][hash_ip(target)] = rp->next;
  358.  
  359.     free((char *)rp);
  360.     return 0;
  361. }
  362.  
  363. /* Compute hash function on IP address */
  364. static int16
  365. hash_ip(addr)
  366. register int32 addr;
  367. {
  368.     register unsigned int ret;
  369.  
  370.     ret = hiword(addr);
  371.     ret ^= loword(addr);
  372.     return ret % NROUTE;
  373. }
  374. #ifndef    GWONLY
  375. /* Given an IP address, return the MTU of the local interface used to
  376.  * reach that destination. This is used by TCP to avoid local fragmentation
  377.  */
  378. int16
  379. ip_mtu(addr)
  380. int32 addr;
  381. {
  382.     register struct route *rp;
  383.     struct iface *iface;
  384.  
  385.     rp = rt_lookup(addr);
  386.     if(rp == NULLROUTE || rp->iface == NULLIF)
  387.         return 0;
  388.  
  389.     iface = rp->iface;
  390.     if(iface->forw != NULLIF)
  391.         return iface->forw->mtu;
  392.     else
  393.         return iface->mtu;
  394. }
  395. #endif
  396. /* Look up target in hash table, matching the entry having the largest number
  397.  * of leading bits in common. Return default route if not found;
  398.  * if default route not set, return NULLROUTE
  399.  */
  400. static struct route *
  401. rt_lookup(target)
  402. int32 target;
  403. {
  404.     register struct route *rp;
  405.     int bits;
  406.     int32 tsave;
  407.     int32 mask;
  408.  
  409.     if(target == Rt_cache.target)
  410.         return Rt_cache.route;
  411.  
  412.     tsave = target;
  413.  
  414.     mask = ~0;    /* All ones */
  415.     for(bits = 31;bits >= 0; bits--){
  416.         target &= mask;
  417.         for(rp = Routes[bits][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  418.             if(rp->target == target){
  419.                 /* Stash in cache and return */
  420.                 Rt_cache.target = tsave;
  421.                 Rt_cache.route = rp;
  422.                 return rp;
  423.             }
  424.         }
  425.         mask <<= 1;
  426.     }
  427.     if(R_default.iface != NULLIF){
  428.         Rt_cache.target = tsave;
  429.         Rt_cache.route = &R_default;
  430.         return &R_default;
  431.     } else
  432.         return NULLROUTE;
  433. }
  434. /* Convert IP header in host format to network mbuf */
  435. struct mbuf *
  436. htonip(ip,data)
  437. struct ip *ip;
  438. struct mbuf *data;
  439. {
  440.     int16 hdr_len;
  441.     struct mbuf *bp;
  442.     register char *cp;
  443.     int16 checksum;
  444.     int16 fl_offs;
  445.  
  446.     hdr_len = IPLEN + ip->optlen;
  447.     if((bp = pushdown(data,hdr_len)) == NULLBUF){
  448.         free_p(data);
  449.         return NULLBUF;
  450.     }
  451.     cp = bp->data;
  452.     
  453.     *cp++ = (IPVERSION << 4) | (hdr_len >> 2);
  454.     *cp++ = ip->tos;
  455.     cp = put16(cp,ip->length);
  456.     cp = put16(cp,ip->id);
  457.     fl_offs = ip->offset >> 3;
  458.     if(ip->flags.df)
  459.         fl_offs |= 0x4000;
  460.     if(ip->flags.mf)
  461.         fl_offs |= 0x2000;
  462.  
  463.     cp = put16(cp,fl_offs);
  464.     *cp++ = ip->ttl;
  465.     *cp++ = ip->protocol;
  466.     cp = put16(cp,0);    /* Clear checksum */
  467.     cp = put32(cp,ip->source);
  468.     cp = put32(cp,ip->dest);
  469.     if(ip->optlen != 0)
  470.         memcpy(cp,ip->options,ip->optlen);
  471.  
  472.     /* Compute checksum and insert into header */
  473.     checksum = cksum(NULLHEADER,bp,hdr_len);
  474.     put16(&bp->data[10],checksum);
  475.  
  476.     return bp;
  477. }
  478. /* Extract an IP header from mbuf */
  479. int
  480. ntohip(ip,bpp)
  481. struct ip *ip;
  482. struct mbuf **bpp;
  483. {
  484.     int16 ihl;
  485.     int16 fl_offs;
  486.     char ipbuf[IPLEN];
  487.  
  488.     if(pullup(bpp,ipbuf,IPLEN) != IPLEN)
  489.         return -1;
  490.  
  491.     ip->version = (ipbuf[0] >> 4) & 0xf;
  492.     ip->tos = ipbuf[1];
  493.     ip->length = get16(&ipbuf[2]);
  494.     ip->id = get16(&ipbuf[4]);
  495.     fl_offs = get16(&ipbuf[6]);
  496.     ip->offset = (fl_offs & 0x1fff) << 3;
  497.     ip->flags.mf = (fl_offs & 0x2000) ? 1 : 0;
  498.     ip->flags.df = (fl_offs & 0x4000) ? 1 : 0;
  499.     ip->ttl = ipbuf[8];
  500.     ip->protocol = ipbuf[9];
  501.     ip->source = get32(&ipbuf[12]);
  502.     ip->dest = get32(&ipbuf[16]);
  503.  
  504.     ihl = (ipbuf[0] & 0xf) << 2;
  505.     if(ihl < IPLEN){
  506.         /* Bogus packet; header is too short */
  507.         return -1;
  508.     }
  509.     ip->optlen = ihl - IPLEN;
  510.     if(ip->optlen != 0)
  511.         pullup(bpp,ip->options,ip->optlen);
  512.  
  513.     return ip->optlen + IPLEN;
  514. }
  515. /* Perform end-around-carry adjustment */
  516. int16
  517. eac(sum)
  518. register int32 sum;    /* Carries in high order 16 bits */
  519. {
  520.     register int16 csum;
  521.  
  522.     while((csum = sum >> 16) != 0)
  523.         sum = csum + (sum & 0xffffL);
  524.     return (int16) (sum & 0xffffl);    /* Chops to 16 bits */
  525. }
  526. /* Checksum a mbuf chain, with optional pseudo-header */
  527. int16
  528. cksum(ph,m,len)
  529. struct pseudo_header *ph;
  530. register struct mbuf *m;
  531. int16 len;
  532. {
  533.     register unsigned int cnt, total;
  534.     register int32 sum, csum;
  535.     register char *up;
  536.     int16 csum1;
  537.     int swap = 0;
  538.  
  539.     sum = 0l;
  540.  
  541.     /* Sum pseudo-header, if present */
  542.     if(ph != NULLHEADER){
  543.         sum = hiword(ph->source);
  544.         sum += loword(ph->source);
  545.         sum += hiword(ph->dest);
  546.         sum += loword(ph->dest);
  547.         sum += uchar(ph->protocol);
  548.         sum += ph->length;
  549.     }
  550.     /* Now do each mbuf on the chain */
  551.     for(total = 0; m != NULLBUF && total < len; m = m->next) {
  552.         cnt = min(m->cnt, len - total);
  553.         up = (char *)m->data;
  554.         csum = 0;
  555.  
  556.         if(((long)up) & 1){
  557.             /* Handle odd leading byte */
  558.             if(swap)
  559.                 csum = uchar(*up++);
  560.             else
  561.                 csum = (int16)(uchar(*up++) << 8);
  562.             cnt--;
  563.             swap = !swap;
  564.         }
  565.         if(cnt > 1){
  566.             /* Have the primitive checksumming routine do most of
  567.              * the work. At this point, up is guaranteed to be on
  568.              * a short boundary
  569.              */
  570.             csum1 = lcsum((unsigned short *)up, cnt >> 1);
  571.             if(swap)
  572.                 csum1 = (csum1 << 8) | (csum1 >> 8);
  573.             csum += csum1;
  574.         }
  575.         /* Handle odd trailing byte */
  576.         if(cnt & 1){
  577.             if(swap)
  578.                 csum += uchar(up[--cnt]);
  579.             else
  580.                 csum += (int16)(uchar(up[--cnt]) << 8);
  581.             swap = !swap;
  582.         }
  583.         sum += csum;
  584.         total += m->cnt;
  585.     }
  586.     /* Do final end-around carry, complement and return */
  587.     return ~eac(sum) & 0xffff;
  588. }
  589.